package com.rui.study.algorithm.P_不同的二叉搜索树Ⅱ;

import com.rui.study.algorithm.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: study
 * @description:
 * ###思路###
 * 问题的解决依赖于子问题，因此使用分治思想。分治：通过[start, i-1]之间的元素构建所有的左子树，
 * 通过[i+1, end]之间的元素构建右子树。组合：构建i节点，组合所有的左右子树
 * @author: Yaowr
 * @create: 2019-01-15 09:20
 **/
public class Solution2 {

    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> roots;
        if (n == 0) {
            roots = new ArrayList<>();
        } else {
            roots = buildTree(1,n);
        }
        return roots;
    }

    public List<TreeNode> buildTree(int start, int end) {
        List<TreeNode> nodes = new ArrayList<>();
        if (start > end) {
            nodes.add(null);
            return nodes;
        }

        for (int i = start; i <= end; i++) {
            // 分治：分别获取左右子树
            List<TreeNode> leftNodes = buildTree(start, i-1);
            List<TreeNode> rightNodes = buildTree(i+1, end);
            // 组合
            for (TreeNode left : leftNodes) {
                for (TreeNode right : rightNodes) {
                    TreeNode node = new TreeNode(i);
                    node.left = left;
                    node.right = right;
                    nodes.add(node);
                }
            }
        }
        return nodes;
    }

    public static void main(String[] args) {
        long begin = System.currentTimeMillis();
        Solution2 solution = new Solution2();
        List<TreeNode> result = solution.generateTrees(4);
        long end = System.currentTimeMillis();
        System.out.println("不同的二叉搜索树Ⅱ：" + result.size() + ", 耗时：[" + (end - begin) + "ms]");
    }

}
